2018 “百度之星”程序设计大赛 - 初赛（B）

比赛

比赛链接

因为初赛A没过，所以也来体验了B组，感觉还要难一些，也更妙一些。很有收获！

A. degree

首先确定是森林，也就是多棵树。我们枚举作为答案的那个点，首先可以在原来的基础上向剩余的连通块各连一条（即 n - 1 - m，可以脑补一下，如果将剩余的原来是连接连通块的边加上，那么就是一棵 n - 1 条边的树，而每个连通块必然只有一条边连出来，故 n - 1 - m 是可连的连通块数量）。最后再加上别处被移除的边的数量。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int n, m, k, a, b, T;

vector<int> nxt[200005];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        int ans = 0;
        for (int i = 0; i < n; i++) nxt[i].clear();
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &a, &b);
            nxt[a].push_back(b);
            nxt[b].push_back(a);
        }
        for (int i = 0; i < n; i++) {
            int x = nxt[i].size();
            ans = max(ans, x + (n - 1) - m + min(k, m - x));
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. hex

扛了扛，样例未过，不了了之，留坑待填。

C. odds

没仔细看过，留坑待填。

D. p1m2

二分答案！！

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll T, n, a[300005], tmp[300005];

bool chk(ll limit) {
    ll t = 0, sum = 0;
    for (int i = 1; i <= n; i++) tmp[i] = a[i];
    for (int i = 1; i <= n; i++) {
        if (tmp[i] < limit) {
            t += limit - tmp[i];
        } else {
            sum += (tmp[i] - limit) / 2;  // attention!!不是 sum += tmp[i] - limit.
        }
    }
    if (sum >= t) {
        return true;
    }
    return false;
}

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        sort(a + 1, a + n + 1);
        ll l = 0, r = (int)1e8, ans = -1;
        while (l < r) {
            ll mid = (l + r) >> 1;
            if (chk(mid + 1))   // ATTENTION!! WA 3 times for this mistake -- "mid + 1"
                l = mid + 1;
            else r = mid;
        }
        printf("%lld\n", l);
    }
    return 0;
}

E. ratio

并没有做，留坑待填。

F. rect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
----------------
|\            /|
| \     1    / |
|  \        /  |
|   \      /   |
|    \    /    |
|     \  /     |
|  2   \/   3  |
|      /\      |
|     /  \     |
|    /    \    |
|   /      \   |
|  /    4   \  |
| /          \ |
|/            \|
---------------

如图，位于 1 区的线段答案是 x，位于 2 区的线段答案是 y，位于 3 区的线段答案是 my - y，位于 4 区的线段答案是 mx - x，可以证明，绝对不会相交。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mx, my, n, T, x, y, ans;

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld%lld", &mx, &my, &n);
        ans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &x, &y);
            ans += min(x, min(y, min(mx - x, my - y)));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

前500可以进复赛。在还有约30分钟时我是448名左右。当时大概大脑犯抽，一直在想“啊还有12名”，直到我发现了490这个数字的存在。。。